package com.搜索和回溯;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
/*
    因为B的根节点可能是A的任意一个非叶子节点
    因此分成两步：
    第一步：先深度遍历A的每一个节点a
    第二步：判断以a为根节点的子数是否包含了数B

 */
class Solution {
     //判断B是否是A的子结构
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A==null) return false;
        if(B==null) return false;
        boolean reslut=false;
        //判断以A为根节点的子树是否包含了B结构
        reslut=recur(A, B);
        if(reslut==true) return true;
        //如果以A为根节点的子树不包含了B结构，则看看它的左右子树是否包含了B结构
        reslut=isSubStructure(A.left,B)||isSubStructure(A.right,B);
        return reslut;
    }
    public boolean recur(TreeNode A,TreeNode B){
        //循环终止条件
        if(B==null) return true;
        if(A==null || A.val!=B.val) return false;
        //判断A和B的左子树是否相等以及A和B的右子树是否相等
        return recur(A.left,B.left) && recur(A.right,B.right);
    }

}
public class 剑指Offer26树的子结构 {
    public static void main(String[] args) {

    }
}
